#include <iostream>
using namespace std;

// template<typename T>
// void shell_sort(T arr[], int len){
//     int gap = len/3 + 1;  // 间隔--步长
//     T choose;     // 可以认为是选中，要进行插入的牌
//     int preIndex; // 选中的牌的前一个位置（开始进行插入的）

//     while(gap > 0){
//         printf("gap: %d\r\n", gap);
//         // 这里也可以i++
//         for(int i = gap; i < len; i+=gap){
//             choose = arr[i];
//             preIndex = i-gap;
//             while(preIndex >= 0 && arr[preIndex] > choose){
//                 // 如果 arr[preIndex] > choose 大于被选中的牌就后移一位
//                 arr[preIndex+gap] = arr[preIndex];
//                 preIndex -= gap;
//         }
//         // 跳出循环说明，已经找到比手牌还小的数, 插入其后面，且下标为preIndex
//         arr[preIndex+gap] = choose;
//         }
//         gap /= 2;
//     }
// }

// 相比插入排序多了动态步长
template<typename T>
void shell_sort(T arr[], int len){
    int gap;  // 间隔--步长
    T  choose;     // 可以认为是选中，要进行插入的牌
    int preIndex; // 选中的牌的前一个位置（开始进行插入的）

    // 动态步长
    for(gap = len/2; gap>0 ; gap = gap/2){
        printf("gap: %d\r\n", gap);
        // 注意这里还是要i++
        for (int i=gap; i<len; i++){
            choose = arr[i];
            for(preIndex = i-gap; preIndex >=0 && arr[preIndex] > choose; preIndex -= gap){
                arr[preIndex+gap] = arr[preIndex];
            }
            arr[preIndex+gap] = choose;
        }
    }
}


int main() {
        int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
        int len = (int) sizeof(arr) / sizeof(*arr);
        shell_sort(arr, len);
        for (int i = 0; i < len; i++)
                cout << arr[i] << ' ';
        cout << endl;

        float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
        len = (float) sizeof(arrf) / sizeof(*arrf);
        shell_sort(arrf, len);
        for (int i = 0; i < len; i++)
                cout << arrf[i] << ", ";
        cout << endl;
        return 0;
}
